import Tree


class DisjoinSet:
    def __init__(self, initlist):
        """
        :param initlist: the initial list
        :return: None
        """
        # initial self.roots
        self.roots = []
        self.finds = {}
        for i in initlist:
            temp = Tree.TreeNode(value=i)
            self.roots.append(temp)
            self.finds[i] = temp

    def union(self, x, y):
        """
        :rtype Tree.TreeNode
        :param x: the element want to union
        :param y: the element want to union
        :return: if x and y was made to be a union, return False. else union x and y and return True
        """
        if x in self.finds.keys():
            findx = self.finds[x]
        else:
            return False
        if y in self.finds.keys():
            findy = self.finds[y]
        else:
            return False
        tempx = findx
        tempy = findy
        pathx = []
        pathy = []
        if tempx == tempy:
            return False
        while tempx.getparent() is not None:
            pathx.append(tempx)
            tempx = tempx.getparent()
        while tempy.getparent() is not None:
            pathy.append(tempy)
            tempy = tempy.getparent()
        for i in pathx:
            i.setparent(tempx)
            tempx.setchildren(pathx)
        for i in pathy:
            i.setparent(tempy)
            tempy.setchildren(pathy)
        if tempx == tempy:
            return False
        tempy.addchild(tempx)
        tempx.setparent(tempy)
        return True

    def findset(self, x, y):
        """
        :rtype bool
        :param x: the element want to find
        :param y: the element want to find
        :return: x and y in one set or not
        """
        if x in self.finds.keys():
            findx = self.finds[x]
        else:
            return False
        if y in self.finds.keys():
            findy = self.finds[y]
        else:
            return False
        tempx = findx
        tempy = findy
        pathx = []
        pathy = []
        while tempx.getparent() is not None:
            pathx.append(tempx)
            tempx = tempx.getparent()
        while tempy.getparent() is not None:
            pathy.append(tempy)
            tempy = tempy.getparent()
        for i in pathx:
            i.setparent(tempx)
        for i in pathy:
            i.setparent(tempy)
        tempx.setchildren(pathx)
        tempy.setchildren(pathy)
        if tempx == tempy:
            return True
        else:
            return False

if __name__ == '__main__':
    a = DisjoinSet(initlist=[1, 2, 3, 4, 5, 6, 7, 8, 9])
    print(a.union(2, 5))
    print(a.union(7, 9))
    print(a.union(3, 5))
    print(a.union(2, 3))
    print(a.findset(3, 7))
    print(a.findset(3, 4))
    print(a.findset(2, 3))
